package day0204

import "fmt"

func coinChange(coins []int, amount int) int {
	m := len(coins)
	n := amount
	//初始化dp数组
	dp := make([][]int, m)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n+1)
	}
	for i := 0; i < m; i++ {
		for j := 1; j <= n; j++ {
			if coins[i] == j {
				dp[i][j] = 1
			} else {
				res := 0
				for k := 1; k < j; k++ {
					res = min(res, dp[i][k]+dp[i][j-k])
				}
				dp[i][j] = res
			}
		}
	}
	fmt.Println(dp)
	return dp[m-1][n]
}

func min(x, y int) int {
	if x > y {
		return y
	}
	return x
}
